package demo.DataStrucAndAlgo.AlgorithmOfTen;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/7-08-07-10:55
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen     动态规划算法
 */
/*
DP动态规划算法
    将复杂问题拆分成子问题，在子问题的基础上，求解复杂问题，子问题之间不是独立的，而是相互依存的
    动态规划算法的两种实现形式：递归、非递归
递归算法分析：
    约定 weight[] 装载物品的重量，value[] 装载物品的价值。为了方便人机交互，定义上两个数字第一个元素为0。
    装与不装，无非是受背包容量，和价格最大化限制。
    我们假设 OPT(n,i) 代表对第n个物品操作且容量为i时的最优解（价值最大）。那么对于第n个物品而言，受背包容量限制：
    当容量够的时候，我们有两种对n物品的操作，选n，不选n，选n时其对应最优解为 value[n]+OPT(n-1,i-weight[i])，
    不选n时其对应最优解为 OPT(n-1,i)。而此时 OPT(n,i)=MAX{value[n]+OPT(n-1,i-weight[i])，OPT(n-1,i)}
    当容量不够时，我们只有一种对n物品的操作，即不选n。此时OPT(n,i)=OPT(n-1,i)
    以上的运算流程是基于递归完成的。所以要设置递归结束条件：当n==0时，说明没有物品了，return 0;
非递归算法分析：
    将题目中的信息全部整合到一个二维表中，该表对应了容量从4到0的各种情况下的最优解。
    表的第一行，由于价值为0，所以全是0。表的第一列，由于容量为0，所以全是0。
    其他的情况，需要通过程序进行求解。每一个空都对应一种情况，每种情况都受容量限制，每种情况都有两种操作（选与不选）。
    与递归不同的是，这里是自底而上求解（表中从左至右，从上至下）。将每次计算的结果保存在二维数组中，
    求解的下一个结果依赖于上一次已经求好的结果。这就解决了递归式重复计算的问题。
    最终的答案，就在二维数组的右下角。
 */
/*
    01背包问题：
        有个容量为4的背包，有以下3种物品，物品具有价值和重量属性，要求装入的物品价值总和最大且装入物品不能重复
*/
public class DP {
    static int[] value = {0,1500,3000,2000};  //分别对应物品a,b,c,为了方便人机交互，定义第0个物品为0
    static int[] weight= {0,1,4,3};         //分别对应物品a,b,c，定义第0个物品为0
    static int bag = 4;    //背包容量

    public static void main(String[] args) {
        System.out.println(re_OPT(3,4));
        System.out.println(dp_OPT(3,4));

    }

    /**
     * 动态规划，非递归求最优解
     * @param n    第n个物品
     * @param bag   背包容量
     * @return     最优解
     */
    public static int dp_OPT(int n, int bag) {
        int[][] result = new int[weight.length][bag+1];//创建一个二维数组，用来存放各种情况对应的最优解，前[]保存第几个物品，后面[]保存多少背包容量
        //将第一行与第一列重置为0；
        for(int i = 1; i < result.length;i++){
            for(int j = 1; j < result[i].length;j++){
                result[i][j] = j>=weight[i] ? Math.max(value[i]+result[i-1][j-weight[i]],result[i-1][j] ):result[i-1][j];
            }
        }
        return result[n][bag];
    }

    /**
     * 动态规划：递归来求最优解
     * @param n  第n个物品
     * @param bag   背包容量
     * @return   最优解
     */
    public static int re_OPT(int n, int bag) {
        if(n==0){
            return 0;
        }
        if(bag >= weight[n]){
            return Math.max(value[n] + re_OPT(n-1,bag-weight[n]),re_OPT(n-1,bag));
        }else{
            return re_OPT(n-1,bag);
        }
    }
}
